package leetcode

import (
	"Algorithms/datastruct"
	"Algorithms/util"
	"fmt"
	"regexp"
	"strconv"
	"strings"
)

//利用栈实现表达式求值（计算器）
//
// 1.不带括号，符号有优先级
//方法分两个栈，一个存储数字，一个存储符号,遇见数字直接压入
//遇见符号，去和栈顶元素比较，如果栈顶元素优先级高或者相同，则取2个数字和栈顶计算符号计算，计算结果压入数字栈
//如果优先级比栈顶元素高那么就直接入符号栈
//
// 2. 带括号，符号没有优先级，如下，实现和上面差不多，括号判断比较复杂，考虑的情况比较多
//func Calculate(s string) int {
//	var bs = []byte(s)
//	var num_stack = new(datastruct.Stack)
//	var symbol_stack = new(datastruct.Stack)
//
//	for i := 0; i < len(bs); i++ {
//		btostring := string(bs[i])
//		res, ok := util.IsDigital(btostring)
//		if ok {
//			for j := i + 1; j < len(bs); j++ {
//				if res2, ok := util.IsDigital(string(bs[j])); ok {
//					res = res*10 + res2
//					i++
//				} else {
//					break
//				}
//			}
//			num_stack.Push(res)
//		} else if btostring == "+" || btostring == "-" {
//			sout, ok := symbol_stack.Pop()
//			if ok {
//				if sout == "+" {
//					n1, _ := num_stack.Pop()
//					n2, _ := num_stack.Pop()
//					n1int, _ := n1.(int)
//					n2int, _ := n2.(int)
//					num_stack.Push(n1int + n2int)
//					symbol_stack.Push(btostring)
//				} else if sout == "-" {
//					n1, _ := num_stack.Pop()
//					n2, _ := num_stack.Pop()
//					n1int, _ := n1.(int)
//					n2int, _ := n2.(int)
//					num_stack.Push(n2int - n1int)
//					symbol_stack.Push(btostring)
//				} else if sout == "(" {
//					symbol_stack.Push(sout)
//					symbol_stack.Push(btostring)
//				}
//			} else {
//				symbol_stack.Push(btostring)
//			}
//		} else if btostring == "(" {
//			symbol_stack.Push(btostring)
//			if string(bs[i+1]) == "-" {
//				num_stack.Push(0)
//			}
//		} else if btostring == ")" {
//			symbol, _ := symbol_stack.Pop()
//			if symbol != "(" {
//				n1, _ := num_stack.Pop()
//				n2, _ := num_stack.Pop()
//				n1int, _ := n1.(int)
//				n2int, _ := n2.(int)
//				if symbol == "+" {
//					num_stack.Push(n1int + n2int)
//				} else if symbol == "-" {
//					num_stack.Push(n2int - n1int)
//				}
//				symbol, _ = symbol_stack.Pop()
//				if symbol != "(" {
//					return -1
//				}
//			}
//		}
//	}
//	symbol_last, _ := symbol_stack.Pop()
//	if symbol_last == "+" {
//		n1, _ := num_stack.Pop()
//		n2, _ := num_stack.Pop()
//		n1int, _ := n1.(int)
//		n2int, _ := n2.(int)
//		num_stack.Push(n1int + n2int)
//	}
//	if symbol_last == "-" {
//		n1, _ := num_stack.Pop()
//		n1int, _ := n1.(int)
//		n2, ok := num_stack.Pop()
//		if !ok {
//			return n1int * (-1)
//		}
//		n2int, _ := n2.(int)
//		num_stack.Push(n2int - n1int)
//	}
//	n, _ := num_stack.Pop()
//	nint, _ := n.(int)
//	return nint
//}
// 3.该种方法比较简单，因为没有运算符号优先级，那么从左到右计算即可
//遇见括号需要把括号外面的+/-号记录，如果加号则括号里面符号不变号，如果减号则编号，因为有多个括号包含的情况，则需要用到栈来解决
//最里面的括号最先求值，所以最里面的括号的符号应该是后进先出，遇见'('则将前面符号压入栈;遇见')'则将括号弹出栈，以弃用
func Calculate2(s string) int {
	var bs = []byte(s)
	fmt.Println(bs)
	var opt_stack = new(datastruct.Stack)
	sign := 1
	opt_stack.Push(sign)
	i := 0
	res := 0

	for i < len(bs) {
		if string(bs[i]) == "(" {
			opt_stack.Push(sign)
		}
		if string(bs[i]) == "+" {
			sign_temp, _ := opt_stack.Head.Data.(int)
			sign = sign_temp
		}
		if string(bs[i]) == "-" {
			sign_temp, _ := opt_stack.Head.Data.(int)
			sign = sign_temp * (-1)
		}
		if string(bs[i]) == ")" {
			opt_stack.Pop()
		}
		if num, ok := util.IsDigital(string(bs[i])); ok {
			for j := i + 1; j < len(bs); j++ {
				if num_followed, ok := util.IsDigital(string(bs[j])); ok {
					num = num*10 + num_followed
					i++
				} else {
					break
				}
			}
			res += num * sign
		}
		i++
	}

	return res
}

//利用栈实现括号匹配,利用栈的特性来处理
func IsValid(s string) bool {
	var bs = []byte(s)
	var stack = new(datastruct.Stack)
	for _, b := range bs {
		temp := string(b)
		if temp == "(" || temp == "{" || temp == "[" {
			stack.Push(temp)
		} else if temp == ")" {
			other, ok := stack.Pop()
			if !ok || other != "(" {
				return false
			}
		} else if temp == "}" {
			other, ok := stack.Pop()
			if !ok || other != "{" {
				return false
			}
		} else if temp == "]" {
			other, ok := stack.Pop()
			if !ok || other != "[" {
				return false
			}
		} else {
			return false
		}
	}
	if _, ok := stack.Pop(); !ok {
		return true
	}
	return false
}

type fib struct {
	value     int //结果
	nums      int //第几次
	direction int //方向
}

const (
	down = 1
	up   = 2
)

//所有的递归都能用栈结构来实现,而且比递归的时间复杂度低很多
//BenchmarkBenchFib
//BenchmarkBenchFib-16                 403           2951039 ns/op
//BenchmarkFibStack
//BenchmarkFibStack-16              218004              5175 ns/op
func FibStack(n int) int {
	if n <= 0 {
		panic("fib传入参数必须为正整数")
	}
	if n == 2 || n == 1 {
		return 1
	}
	stack := new(datastruct.Stack)
	//构造stack
	//stack中每一项第一个是Record
	//Record第一项是数据（参数或者返回值）
	//Record第二项是递归方向（down=1代表向下递，up=2代表向上归）
	stack.Push(fib{0, n, up})
	stack.Push(fib{0, n, down})

	//栈中只有一项的时候递归停止
	for stack.Size() > 1 {
		f, _ := stack.Pop()
		if f.(fib).direction == down { //向下查找
			//递归终结条件
			if f.(fib).nums == 3 {
				stack.Push(fib{1, 1, up})
				stack.Push(fib{1, 2, up})
				continue
			}
			//传递进入两个，先进一个向上返回的函数，再进一个向下查找的函数
			stack.Push(fib{0, f.(fib).nums - 1, up})
			stack.Push(fib{0, f.(fib).nums - 1, down})
		} else { //向上返回
			f2, _ := stack.Pop()
			f3, _ := stack.Pop()
			if fx, ok := f3.(fib); ok {
				fx.value = f.(fib).value + f2.(fib).value
				//这里前面两个值都需要返回
				stack.Push(fx)
			}
			//这里前面两个值都需要返回
			stack.Push(f2)
		}
	}
	res, _ := stack.Pop()
	return res.(fib).value
}

func BenchFib(n int) int {
	if n <= 0 {
		panic("fib传入参数必须为正整数")
	}
	if n == 1 || n == 2 {
		return 1
	}
	return BenchFib(n-1) + BenchFib(n-2)
}

//1614. 括号的最大嵌套深度
func maxDepth(s string) int {
	stack := []byte{}
	res := 0
	for i := range s {
		if s[i] == '(' {
			stack = append(stack, s[i])
		}
		if s[i] == ')' {
			stack = stack[:len(stack)-1]
		}
		if len(stack) > res {
			res = len(stack)
		}
	}
	return res
}

//71. 简化路径
func simplifyPath(path string) string {
	stack := make([]string, 0)
	paths := strings.Split(path, "/")
	for i := range paths {
		tmp := paths[i]
		switch tmp {
		case ".", "":
			continue
		case "..":
			if len(stack) > 0 {
				stack = stack[:len(stack)-1]
			}
		default:
			stack = append(stack, tmp)
		}
	}
	res := "/"
	for i := range stack {
		res += stack[i]
		if i != len(stack)-1 {
			res += "/"
		}
	}
	return res
}

//22. 括号生成，回溯法
func generateParenthesis(n int) []string {
	var res = new([]string)
	if n <= 0 {
		return *res
	}
	generateParenthesisRecursion("", n, n, res)
	return *res
}

func generateParenthesisRecursion(str string, left, right int, res *[]string) {
	//左右括号都用完了
	if left == 0 && right == 0 {
		*res = append(*res, str)
		return
	}
	//左右括号剩余相等，只能用左括号
	if left == right {
		generateParenthesisRecursion(str+"(", left-1, right, res)
	} else if left < right {
		//两种可能
		//添加左括号
		if left > 0 {
			generateParenthesisRecursion(str+"(", left-1, right, res)
		}
		//添加右括号
		generateParenthesisRecursion(str+")", left, right-1, res)
	}
}

//32. 最长有效括号
func longestValidParentheses(s string) int {
	stack := make([]int, 0)
	stack = append(stack, -1)
	maxLen := 0
	for i := range s {
		if s[i] == '(' {
			stack = append(stack, i)

		} else {
			if len(stack) == 1 || s[stack[len(stack)-1]] == ')' {
				stack = append(stack, i)
			} else {
				stack = stack[:len(stack)-1]
				last := stack[len(stack)-1]
				if maxLen < i-last {
					maxLen = i - last
				}
			}
		}
	}
	return maxLen
}

//150. 逆波兰表达式求值
func evalRPN(tokens []string) int {
	stack := []int{}
	for i := range tokens {
		switch tokens[i] {
		case "+":
			tmp := stack[len(stack)-2] + stack[len(stack)-1]
			stack = stack[:len(stack)-2]
			stack = append(stack, tmp)
		case "-":
			tmp := stack[len(stack)-2] - stack[len(stack)-1]
			stack = stack[:len(stack)-2]
			stack = append(stack, tmp)
		case "*":
			tmp := stack[len(stack)-2] * stack[len(stack)-1]
			stack = stack[:len(stack)-2]
			stack = append(stack, tmp)
		case "/":
			tmp := stack[len(stack)-2] / stack[len(stack)-1]
			stack = stack[:len(stack)-2]
			stack = append(stack, tmp)
		default:
			tmp, _ := strconv.ParseInt(tokens[i], 10, 32)
			stack = append(stack, int(tmp))
		}
	}
	return stack[0]
}

//394. 字符串解码
func decodeString(s string) string {
	stackNum := []int{}
	stackStr := []string{}
	sampleRegexp := regexp.MustCompile(`\d`)
	sampleRegexp2 := regexp.MustCompile(`[a-z]`)
	for i := 0; i < len(s); {
		if sampleRegexp.MatchString(string(s[i])) {
			j := i + 1
			for ; j < len(s); j++ {
				if !sampleRegexp.MatchString(string(s[j])) {
					break
				}
			}
			x, _ := strconv.ParseInt(s[i:j], 10, 64)
			stackNum = append(stackNum, int(x))
			i = j
		} else if s[i] == '[' {
			stackStr = append(stackStr, "[")
			i++
		} else if s[i] == ']' {
			num := stackNum[len(stackNum)-1]
			stackNum = stackNum[:len(stackNum)-1]
			str:=""
			for stackStr[len(stackStr)-1]!="["{
				str = stackStr[len(stackStr)-1]+str
				stackStr = stackStr[:len(stackStr)-1]
			}
			stackStr = stackStr[:len(stackStr)-1]
			tmp:=""
			for k := 0; k < num; k++ {
				tmp += str
			}
			stackStr=append(stackStr, tmp)
			i++
		} else {
			j := i + 1
			for ; j < len(s); j++ {
				if !sampleRegexp2.MatchString(string(s[j])) {
					break
				}
			}
			stackStr = append(stackStr, s[i:j])
			i = j
		}
	}
	res:=""
	for i:=range stackStr {
		res += stackStr[i]
	}
	return res
}
